/*
 * CopyRight(C) Kenbin
 */

#ifndef LSG_BUDDYBIT_INCLUDED
#define LSG_BUDDYBIT_INCLUDED

/*Comment#
   buddy(伙伴)算法是一种空间块分配算法，其特点是分配的空间块数量N必须是2的
   倍数，分配的起始块偏移位置必须刚好被N整除。

   在本实现中，分配的空间块block是文件中的数据块。

   buddybit是一个block状态的记录序列，每个block占用两个bit位，buddybit[2K]
   标识block[K]是否被分配，buddybit[2K+1]标识block[K]是否和block[K-1]同属
   一个连续分配区间。

   buddybit可以存储在每个文件头部分，固定长度。

   通过buddybit可以构造两个完全二叉树用于管理block的分配。假设管理的block
   数量为N，2^(m-1) < N <= 2^m，则完全二叉树的深度为m层，每一层把N个block
   分为不同尺寸的slot集合，第一层有1个slot，slot的尺寸为2^m个block；第二层
   有2个slot，slot的尺寸为2^(m-1)个block；依此类推，第K层有2^(K-1)个slot，
   slot的尺寸为2^(m-K+1)个block，第m层有2^(m-1)个slot，slot尺寸为2。

   slot_class = m - 1。

   完全二叉树的每个节点记录其左右子节点的使用情况，其中一颗树的节点值为1
   表示其左右两个子节点都是空闲的；另一颗树的节点值为1表示其左右子节点都
   已经被占用。
*/

namespace LSG {

    class CBuddyBit
    {
	public:
	    CBuddyBit(char *buddybit, int bytes);
	    ~CBuddyBit();

	    int Alloc(int block_count, int *byte_offset, int *bytes);
	    void Free(int buddybit_offset, int *byte_offset, int *bytes);

	    int SlotItemSize(int buddybit_offset);
	    int Alloced();

	    char *BuddyBit() { return m_buddybit; }

	    void PrintInfo();

	private:
	    int get_free_slot_item(int block_count, int slot_class = 1, int buddybit_offset = 0);

	    void flush_buddybit(int buddybit_offset, int block_count, int value);
	    int flush_tree(int buddybit_offset, int block_count);

	    inline int getbit(char *bit, int bit_offset);
	    inline void setbit(char *bit, int bit_offset, int value);

	    char *m_buddybit; /* buddybit is 2 bit per block */
	    int m_buddybit_total;
	    int m_buddybit_alloced;

	    int m_total_slot_class;
	    int *m_slot_item_count;
	    int *m_slot_item_size;
	    char **m_free_tree;
	    char **m_occupied_tree;
    };

};

#endif

